package collections.tree;

import java8.TreePrintUtil;

public class MyBST {

    public static void main(String[] args) {
        MyBST bst = new MyBST();
        bst.insert(10);
        bst.insert(17);
        bst.insert(11);
        bst.insert(14);
//        bst.insert(12);
        bst.insert(3);
        bst.insert(33);
        bst.insert(38);
        bst.insert(0);
        bst.insert(99);
        bst.insert(100);
        bst.insert(15);
        TreePrintUtil.pirnt(bst.root);

        System.out.println("删除99");
        bst.remove(99);
        TreePrintUtil.pirnt(bst.root);

        System.out.println("再删除17");
        bst.remove(17);
        TreePrintUtil.pirnt(bst.root);
    }

    Node root;

    public void insert(int key) {
        Node lastParent = null;
        Node tmp = root;
        if (root == null) {
            Node n = new Node();
            n.key = key;
            root = n;
            return;
        }

        while (tmp != null) {
            lastParent = tmp;
            if (key < tmp.key) {
                tmp = tmp.left;
            } else {
                tmp = tmp.right;
            }
        }

        Node n = new Node();
        n.parent = lastParent;
        n.key = key;
        if (lastParent.key < key) {
            lastParent.right = n;
        } else {
            lastParent.left = n;
        }
    }

    public void remove(int key) {
        Node tmp = root; // 要删除掉的节点
        if (root == null) {
            return;
        }

        while (tmp != null) {
            if (tmp.key == key) {
                break;
            } else if (key < tmp.key) {
                tmp = tmp.left;
            } else {
                tmp = tmp.right;
            }
        }

        // 删除的节点没有左右节点
        if (tmp.left == null && tmp.right == null) {
            if (tmp == tmp.parent.left) {
                tmp.parent.left = null;
            } else {
                tmp.parent.right = null;
            }
            return;
        }

        // 删除的节点只有1个子节点
        if (tmp.left == null) { // tmp有右孩子
            if (tmp == tmp.parent.left) { // tmp是父的左节点
                tmp.parent.left = tmp.right;
                tmp.right.parent = tmp.parent;
            } else { // tmp是父的右节点
                tmp.parent.right = tmp.right;
                tmp.right.parent = tmp.parent;
            }
        } else if (tmp.right == null) { // tmp有左孩子
            if (tmp == tmp.parent.left) { // tmp是父的左节点
                tmp.parent.left = tmp.left;
                tmp.left.parent = tmp.parent;
            } else { // tmp是父的右节点
                tmp.parent.right = tmp.left;
                tmp.left.parent = tmp.parent;
            }
        } else { // tmp 2个子节点都不空
            Node successor = findSuccessor(tmp);
            Node successorParent = successor.parent;

            successor.parent = tmp.parent;
            if (tmp.parent.left == tmp) {
                tmp.parent.left = successor;
            }
            if (tmp.parent.right == tmp) {
                tmp.parent.right = successor;
            }

            if (successor.left != null) {
                if (successor == successorParent.left) {
                    successorParent.left = successor.left;
                    successor.left.parent = successorParent;
                } else {
                    successorParent.right = successor.left;
                    successor.left.parent = successorParent;
                }
            } // successor不可能有右节点

            tmp.left.parent = successor;
            successor.left = tmp.left;
            tmp.right.parent = successor;
            successor.right = tmp.right;
            if(successorParent.right == successor) {
                successorParent.right = null;
            }
        }
    }

    /**
     * 找到接班人
     *
     * @param n
     * @return
     */
    public Node findSuccessor(Node n) {
        Node result = null;
        Node left = n.left;
        Node right = n.right;
        while (left != null) {
            result = left;
            left = left.right;
        }
        if (result != null) {
            return result;
        }

        while (right != null) {
            result = right.left;
            right = right.left;
        }
        return result;

    }


    static class Node implements TreePrintUtil.TreeNode {
        int key;
        Node left;
        Node right;
        Node parent;


        @Override
        public String getPrintInfo() {
            return key + "";
        }

        @Override
        public TreePrintUtil.TreeNode getLeftChild() {
            return left;
        }

        @Override
        public TreePrintUtil.TreeNode getRightChild() {
            return right;
        }

        public String toString() {
            return "[" + key + "]";
        }
    }
}
